package struct.string;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * @author: kanggw
 * @date: 2022/3/22
 * @DESCRIPTION:
 * 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa503c/
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

 */
public class WordSplit {

    private static Map<String, Boolean> checkedStr = Maps.newHashMap();

    public static void main(String[] args) {

        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
//        final ArrayList<String> wordDict = Lists.newArrayList("leet", "code");
        final ArrayList<String> wordDict = Lists.newArrayList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa");

        final Boolean process = process(s, wordDict);
        System.out.println("out:" + process);
    }

    public static Boolean process(String s, List<String> wordDict) {

        if (s.length() == 0 || wordDict.isEmpty()) return false;

        return backUp(s, wordDict);
    }

    private static boolean backUp(String s, List<String> wordDict) {

        final Boolean aBoolean = checkedStr.get(s);

        if (null != aBoolean) {
            return aBoolean;
        }
        for (int i = 0; i < s.length(); i++) {
            if (wordDict.contains(s.substring(0, i + 1))) {
                if (i + 1 >= s.length()) {
                    return true;
                }
                checkedStr.put(s.substring(0, i + 1), true);
                if (backUp(s.substring(i + 1), wordDict)) {
                    return true;
                }

            }
            checkedStr.put(s.substring(0, i + 1), false);

        }

        return false;
    }
}

 class Solution {

     public static void main(String[] args) {
         String s = "aaaaaaaaaaaaaab";
//        final ArrayList<String> wordDict = Lists.newArrayList("leet", "code");
         final ArrayList<String> wordDict = Lists.newArrayList("a", "aa","aaa");
         Solution solution = new Solution();
         final boolean b = solution.wordBreak(s, wordDict);

         System.out.println("out:"+ b);
     }
    public boolean wordBreak(String s, List<String> wordDict) {
        // 参考高赞题解的 dfs
        // 1: 访问且为 true  -1: 访问且为 false
        int[] visited = new int[s.length() + 1];
        return dfs(s, 0, wordDict, visited);
    }

    public boolean dfs(String s, int start, List<String> wordDict, int[] visited) {
        // start 来到字符串末尾的「下一位」 说明匹配成功
        if (start == s.length())
            return true;

        // 剪枝 防止重复计算
        if (visited[start] == 1)
            return true;
        if (visited[start] == -1)
            return false;

        for (int end = start + 1; end <= s.length(); end++) {
            String pre = s.substring(start, end);
            if (wordDict.contains(pre) &&
                    dfs(s, end, wordDict, visited)) {
                // 标记匹配成功
                visited[start] = 1;
                return true;
            }
        }
        // 标记匹配失败
        visited[start] = -1;
        return false;
    }
}
